package leetcode.L500;

public class EX74 {
    public  boolean searchMatrix(int[][] matrix, int target) {

        int m = matrix.length;
        int n = matrix[0].length;

        int left = 0;
        int right = m-1;
        while (left<right){
            int mid = left+(right-left+1)/2;
            if(matrix[mid][0]==target){
                return true;
            }
            else if(matrix[mid][0]<target){
                left = mid;
            }
            else if(matrix[mid][0]>target){
                right = mid-1;
            }
        }
        int d = left;
        left = 0;
        right = n-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(matrix[d][mid]==target){
                return true;
            }
            else if(matrix[d][mid]<target){
                left = mid+1;
            }
            else if(matrix[d][mid]>target){
                right = mid-1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] m = {{1, 3, 5, 7}, {10, 11, 16, 20}, {3, 30, 34, 60}};
        EX74 ex74 = new EX74();
        boolean b = ex74.searchMatrix(m, 13);

    }
}
